package bishi.day15_5_11;

import java.util.*;

/**
 * @author 是阿秋啊
 * @date 2022/05/12 13:51
 **/

/**
 * 解题思路
 * 第一，左右手中，如果有一种颜色一边手套为0，则另一边手套取时，最少要加上该种颜色的所有
 * 第二，选出筛选出左右手都不为0的种类后，选出左右手套数较小的一边，进行主要拿取
 * 第三，拿取（这里的拿取指在第二步中选出，要从那一边手中取手套）时，从多数（指该手颜色种数最多的）到少数开始拿，
 *      到最少的颜色手套数时，不需要加上所有，只需加1即可
 * 第四，加完之后，相当于较少一边的手套任何种类都有了，则只需要在另一边任意取一个即可（这里指的是经过第一步筛选后）
 */
public class Gloves {
    public static void main(String[] args) {
        System.out.println(findMinimum(6,new int[]{1,2,0,1,3,1},new int[]{0,0,0,2,0,1}));
    }
    public static int findMinimum(int n, int[] left, int[] right) {
        // write code here
        n = 0;
        for (int i = 0; i < left.length; i++) {
            if (left[i] == 0) {
                n += right[i];
                right[i] = 0;
            }
            if (right[i] == 0) {
                n += left[i];
                left[i] = 0;
            }
        }
        int lSum = Arrays.stream(left).sum();
        int rSum = Arrays.stream(right).sum();
        if (lSum > rSum) {
             n = helper(n,left,right);
        }else {
             n = helper(n,right,left);
        }
        return n;
    }
    public static int helper(int n,int[] max,int[] min) {
        // 下标0代表max，下标1代表min
        Arrays.sort(min);
        for (int i = min.length - 1; i >= 1; i--) {
            if (min[i - 1] == 0) {
                n+=1;
                break;
            }
            n+=min[i];
        }
        if (min[0] != 0) {
            n+=1;
        }
        n+=1;
        return n;
    }
    // 简洁的解题代码，非java语言
//    class Gloves {
//        public:
//        int findMinimum(int n, vector<int> left, vector<int> right) {
//            // write code here
//            int sum=0;
//            int leftSum=0,rightSum=0;
//            int leftMin=30,rightMin=30;
//            for(int i=0;i<n;i++)
//            {
//                if(left[i]*right[i]==0)sum+=(left[i]+right[i]);
//                else{
//                    leftSum+=left[i];
//                    rightSum+=right[i];
//                    leftMin = min(leftMin,left[i]);
//                    rightMin = min(rightMin,right[i]);
//                }
//            }
//            return sum + min(leftSum-leftMin+1,rightSum-rightMin+1) + 1;
//        }
//    };
}